package com.LeetCode.List;

import org.junit.Test;

/**
 * 链表相加
 */
public class AddInList {

    public ListNode addInList (ListNode head1, ListNode head2) {
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        int carry = 0;
        int sum = 0;
        while(head1 != null || head2 != null){
            int num1 = head1 == null ? 0 : head1.val;
            int num2 = head2 == null ? 0 : head2.val;
            sum = carry + num1 + num2;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            carry = sum / 10;
            if(head1 != null) head1 = head1.next;
            if(head2 != null) head2 = head2.next;
        }
        if(carry > 0){
            cur.next = new ListNode(carry);
        }
        return reverseList(head.next);
    }

    private ListNode reverseList(ListNode head){
        ListNode pNode = head;
        ListNode prev = null;
        while(pNode != null){
            ListNode next = pNode.next;
            pNode.next = prev;
            prev = pNode;
            pNode = next;
        }
        return prev;
    }

    @Test
    public void test(){
        ListNode node1 = new ListNode(9);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(7);
        ListNode node4 = new ListNode(6);
        ListNode node5 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        node4.next = node5;
        ListNode.printList(addInList(node1, node4));
    }
}
